We now select the node with the minimum current distance from the Priority Queue, which is guaranteed to be the shortest path.

  • The Priority Queue ($\text{pq}$) currently holds the entries $\text{[(1, 'B'), (4, 'C')]}$. We extract the minimum: (1, 'B').
  • Node B is confirmed as visited, finalizing its shortest distance $d[B]=1$. This is the core greedy choice of Dijkstra's.
  • We examine neighbors of B: C and D, starting the relaxation process to see if B offers a shorter path to them.
  • For neighbor C: The path $A \to B \to C$ has cost $1 + 2 = 3$. Since $3 < d[C]=4$, we update $d[C]$ to 3.
  • The new, shorter path $(3, 'C')$ is added to the $\text{pq}$. The old, stale entry $(4, 'C')$ remains until popped later.
  • For neighbor D: The path $A \to B \to D$ has cost $1 + 5 = 6$. Since $6 < d[D]=\infty$, we update $d[D]$ to 6.
  • The $\text{pq}$ now contains entries for $C$ (distance 3), the stale $C$ (distance 4), and $D$ (distance 6).
Current State of Distance Arrays